import heapq
import math

_ = float('inf')


def branch(graph: list[list[int]], source: int) -> list[int]:
    """
    :param graph: 图的邻接矩阵
    :param source: 源点索引
    :return: 距离最小值
    """
    heap = []
    length = [math.inf for _ in range(len(graph))]
    length[source] = 0
    heapq.heappush(heap, (length[source], source))
    while len(heap) != 0:
        tmp = heapq.heappop(heap)
        if tmp[0] <= length[tmp[1]]:
            for i in range(len(graph)):
                if graph[tmp[1]][i] + tmp[0] < length[i]:
                    length[i] = graph[tmp[1]][i] + tmp[0]
                    heapq.heappush(heap, (length[i], i))
    return length


if __name__ == '__main__':
    graph = [
        [0, 4, 2, 5, _, _, _, _, _, _],
        [_, 0, _, _, 7, 5, _, _, _, _],
        [_, _, 0, _, _, 9, _, _, _, _],
        [_, _, _, 0, 2, _, 7, _, _, _],
        [_, _, _, _, 0, _, _, 4, _, _],
        [_, _, _, _, _, 0, _, _, _, 6],
        [_, _, _, _, _, _, 0, _, 3, _],
        [_, _, _, _, _, _, _, 0, _, 7],
        [_, _, _, _, _, _, _, _, 6, 8],
        [_, _, _, _, _, _, _, _, _, 0]
    ]
    print(branch(graph, 0))
